#include "filesys/cache.h"
#include <debug.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>
#include "threads/thread.h"
#include "threads/malloc.h"
#include "filesys/file.h"
#include "filesys/filesys.h"
#include "filesys/inode.h"
#include "devices/timer.h"
#include "devices/disk.h"


struct cache cache_block[BUF_SIZE];

int read_ahaed_sector_idx;
int dirty_counter;

void cache_init(void){
	int i;
	for(i=0; i<BUF_SIZE; i++){
		cache_block[i].sector_idx = -1;
		cache_block[i].dirtyBit = cache_block[i].accessBit = cache_block[i].allocateBit = false;
		lock_init(&cache_block[i].cache_lock);
	}
	read_ahaed_sector_idx = -1;
	sema_init(&sector_sema,1);

	dirty_counter = 0;

//	thread_create("cache_flush_thread", PRI_DEFAULT-1, cache_flush_thread, NULL);
}

int cache_finder(int sector_idx, bool want_lock){
	int i;
	for(i=0; i<BUF_SIZE; i++){
		lock_acquire(&cache_block[i].cache_lock);
		if( cache_block[i].allocateBit && cache_block[i].sector_idx == sector_idx){
			// returned with holding lock
			if(!want_lock)
				lock_release(&cache_block[i].cache_lock);
			return i;
		}
		lock_release(&cache_block[i].cache_lock);
	}

	return -1;
}

void cache_read(int sector_idx, int offset, int read_byte, void *bounce)
{
	int pos;
	
	sema_down(&sector_sema);

	pos = cache_finder(sector_idx, true);

	// cache miss
	if(pos == -1){

		// find an empty slot
		pos = find_empty_slot();
		
		// no empty slot, so sth should be evicted
		if(pos == -1){
			pos = evict_cache_slot();
		}
		
		// write a block from disk to cache
		cache_block[pos].sector_idx = sector_idx;
		cache_block[pos].allocateBit = true;
		cache_block[pos].accessBit = true;
		sema_up(&sector_sema);
		
		disk_read(filesys_disk, cache_block[pos].sector_idx, cache_block[pos].buffer);
	}
	else{
		// mark as accessed whether cache is hit or miss(after updated in this case)
		cache_block[pos].accessBit = true;
		sema_up(&sector_sema);
	}

	memcpy(bounce, cache_block[pos].buffer + offset, read_byte);
	
	lock_release(&cache_block[pos].cache_lock);
	
	if( sector_idx == (int)disk_size( filesys_disk ) ){
		return;
	}

	read_ahaed_sector_idx = sector_idx+1;
	
	sema_down(&sector_sema);
	pos = cache_finder(read_ahaed_sector_idx, false);

	// cache miss
	if(pos == -1){

		// find an empty slot
		pos = find_empty_slot();
		
		// no empty slot, so sth should be evicted
		if(pos == -1){
			pos = evict_cache_slot();
		}
		
		// write a block from disk to cache
		cache_block[pos].sector_idx = read_ahaed_sector_idx;
		cache_block[pos].allocateBit = true;
		cache_block[pos].accessBit = true;	
		sema_up(&sector_sema);

		disk_read(filesys_disk, cache_block[pos].sector_idx, cache_block[pos].buffer);
		lock_release(&cache_block[pos].cache_lock);

	}
	else{
		sema_up(&sector_sema);
	}

}

void cache_write(int sector_idx, int offset, int read_byte, void *bounce){
	int pos;
	
	sema_down(&sector_sema);
	pos = cache_finder(sector_idx, true);
	
	// cache miss
	if(pos == -1){
		// find an empty slot
		pos = find_empty_slot();
		
		// no empty slot, so sth should be evicted
		if(pos == -1){
			pos = evict_cache_slot();
		}
		
		// write a block from disk to cache
		cache_block[pos].sector_idx = sector_idx;
		cache_block[pos].allocateBit = true;
		cache_block[pos].accessBit = true;
		cache_block[pos].dirtyBit = true;
		sema_up(&sector_sema);
		disk_read(filesys_disk, cache_block[pos].sector_idx, cache_block[pos].buffer);
	}
	else{
		cache_block[pos].accessBit = true;
		cache_block[pos].dirtyBit = true;
		sema_up(&sector_sema);
	}
	memcpy(cache_block[pos].buffer + offset, bounce, read_byte);
	dirty_counter++;

	lock_release(&cache_block[pos].cache_lock);
}

int find_empty_slot(void){
	int i;
	for(i=0; i<BUF_SIZE; i++){
		lock_acquire(&cache_block[i].cache_lock);
		if( !cache_block[i].allocateBit ){
			// returned with holding lock
			return i;
		}
		lock_release(&cache_block[i].cache_lock);
	}

	return -1;
}

int evict_cache_slot(void){
	static int start = 0;
	int i;

	for (i = start; ( i = i% BUF_SIZE ) | 1 ; ++i)
	{
        lock_acquire(&cache_block[i].cache_lock);
		// find a cache block to evict
		if(!cache_block[i].accessBit){
			start = (i+1)%BUF_SIZE;
			break;
		}
		cache_block[i].accessBit = false;
		lock_release(&cache_block[i].cache_lock);
	}
	
	// always holds a lock with available index number.
	// this fact is important cuz if lock is not holded, then flush thread will do write operation

	// if the cache block is dirty, than do the write back
	if(cache_block[i].dirtyBit){
		disk_write(filesys_disk, cache_block[i].sector_idx, cache_block[i].buffer);
		dirty_counter--;
	}

	cache_block[i].sector_idx = -1;
	cache_block[i].dirtyBit = false;
	cache_block[i].accessBit = false;
	cache_block[i].allocateBit = false;

	return i;
}

void flush_cache_blocks(void){
	int i;
	// do the flushing
	for(i=0; i<BUF_SIZE; i++){
		lock_acquire(&cache_block[i].cache_lock);
		if( cache_block[i].allocateBit && cache_block[i].dirtyBit ){
			disk_write(filesys_disk, cache_block[i].sector_idx, cache_block[i].buffer);
			cache_block[i].dirtyBit = false;
		}
		lock_release(&cache_block[i].cache_lock);
	}
}

void cache_flush_thread(void *aux UNUSED){
	while(true){
		if(dirty_counter > BUF_SIZE/2){
			flush_cache_blocks();
			dirty_counter = 0;
		}
		thread_yield();
	}
}

void cache_remove(int idx){
	int pos = cache_finder(idx, true);
	if(pos != -1){
		cache_block[pos].sector_idx = -1;
		cache_block[pos].dirtyBit =	cache_block[pos].accessBit = cache_block[pos].allocateBit = false;
		lock_release(&cache_block[pos].cache_lock);
	}
}
